package code.mySpecializedTraining;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 26029
 * @date 2025/4/22
 * @description
 */
public class UnionSet {
    // 399. 除法求值
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 构建并查集
        // equations = [["a","b"],["b","c"]]
        // values = [2.0,3.0]
        Map<String, Integer> map = new HashMap<>();
        int size = equations.size();
        UniFind uniFind = new UniFind(2 * size);
        int count = 0;
        for (int i = 0; i < size; i++) {
            List<String> equation = equations.get(i);
            if (!map.containsKey(equation.get(0))) {
                map.put(equation.get(0), count);
                count++;
            }
            if (!map.containsKey(equation.get(1))) {
                map.put(equation.get(1), count);
                count++;
            }
            uniFind.union(map.get(equation.get(0)), map.get(equation.get(1)) , values[i]);
        }
        // 查询
        // queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
        size = queries.size();
        double[] ans = new double[size];
        for (int i = 0; i < size; i++) {
            List<String> query = queries.get(i);
            if (!map.containsKey(query.get(0)) || !map.containsKey(query.get(1))) {
                ans[i] = -1.0;
                continue;
            }
            int x = map.get(query.get(0));
            int y = map.get(query.get(1));
            if (uniFind.isSameGroup(x, y))
                ans[i] = uniFind.weight[x] / uniFind.weight[y];
            else
                ans[i] = -1.0;
        }

        return ans;
    }

    private class UniFind {
        private int[] parent;
        private double[] weight;

        public UniFind(int size) {
            parent = new int[size];
            weight = new double[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                weight[i] = 1.0;
            }
        }

        public int find(int i) {
            if (parent[i] != i) {
                int origin = parent[i];
                parent[i] = find(parent[i]);
                weight[i] *= weight[origin];
            }
            return parent[i];
        }

        public void union(int x, int y, double value) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY)
                return;
            parent[rootX] = rootY;
            weight[rootX] = value * weight[y] / weight[x];
        }

        public boolean isSameGroup(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            return rootX == rootY;
        }
    }
}
